\chapter{Minimizaci\'on de energ\'ia mediante Graph Cuts}
\label{ch:graphcuts}

Dadas las diferentes modalidades a partir las cuales se pretende obtener una
segmentaci\'on de los tejidos y los componentes posibles a encontrar en un tumor,
?`como realizamos los c\'alculos y que m\'etodos entran en juego? En este
cap\'itulo analizaremos como convertimos el problema de segmentaci\'on de un
estudio de resonancia magn\'etica en una minimizaci\'on de energ\'ia, y como
resolvemos dicha minimizaci\'on mediante nuestro algoritmo.\\
En este capitulo presentamos el problema de segmentaci\'on de im\'agenes y las
posibles aproximaciones a una soluci\'on.\\
Luego analizamos el funcional de energ\'ia y demostramos que buscar su
minimizaci\'on es an\'alogo a realizar cortes m\'inimos en un grafo construido
de determinada forma a partir de las im\'agenes a segmentar \viewref{sec:modelo}.\\
Finalmente mostramos la funci\'on de etiquetado elegida, y mostramos que
satisface las propiedades requeridas por el modelo \viewref{sec:funcionDeEtiquetado}.\\

\section{{\color{blue}El modelo de segmentaci\'on}}
\label{sec:modelo}

\subsection{{\color{blue}El funcional de energ\'ia}}
\label{sec:funcional}

Como vimos en \ref{sec:introduccion}, los problemas de segmentaci\'on de
im\'agenes son normalmente planteados en t\'erminos de minimizaci\'on de
energ\'ia \viewref{sec:energia}. Dada la definici\'on de funci\'on de etiquetado
\cite{Boykov2001}, nuestro objetivo consiste en encontrar el etiquetado $f$ que
minimize el funcional

\begin{equation} \label{eq:funcional}
E(f) = E_{smooth}(f) + E_{data}(f)
\end{equation}

\begin{comment}
\begin{tip}{Etiquetas}
Para hablar de caraster\'isticas compartidas entre
diferentes v\'oxeles utilizamos el t\'ermino \graphLabel,
de modo que a cada v\'oxel $p \in \W$ (siendo $\W$ el plano donde se define la
imagen que estamos analizando) le asignamos una \graphLabel perteneciente a
un conjunto finito de etiquetas $\L$. Parte de nues\-tro objetivo consiste en
encontrar una funci\'on $f$ que asigne a cada v\'oxel $p \in \W$ una
\graphLabel $f_p \in \L$ \cite{Boykov2001}.
\end{tip}
\end{comment}

En \mathref{eq:funcional} se encuentran los dos factores que buscamos cuantificar
y luego mini\-mizar. Los mismos hacen de $f$ una funci\'on \piecewiseSmooth y
consistente con la imagen. $E_{smooth}(f)$ se encarga de medir cuan suave (o
constante) es la segmentaci\'on \viewref{sec:suavidad} y representa la sumatoria

\begin{displaymath}
E_{smooth}(f) = \sum_{\{p,q\} \in N} V_{p,q}(f_p,f_q)
\end{displaymath}

donde $\N$ es el conjunto de ``pares de v\'oxeles relacionados''
\cite{Boykov2001}. En nuestro modelo utilizamos la adyacencia entre cada par de
v\'oxeles para determinar si est\'an relacionados o no
\viewref{sec:vecindario}.\\ Llamamos $V$ a la \penaltyFunction, encargada de
asignar valores a la relaci\'on entre cada par de v\'oxeles
\viewref{sec:suavidad} \cite{Boykov2001}.

$E_{data}(f)$ nos permite medir cuan parecida es la segmentaci\'on a la
imagen original. Para ello armamos una funci\'on $D$ que mide cuan bien
aproxima \graphLabel $f_p$, las caracter\'isticas del v\'oxel $p$ en la imagen.

\begin{displaymath}
E_{data}(f) = \sum_{p \in \W} D_p(f_p)
\end{displaymath}

Finalmente el funcional se expresa

\begin{displaymath}
E(f) = \sum_{\{p,q\} \in \N} V_{p,q}(f_p,f_q) + \sum_{p \in \W} D_p(f_p)
\end{displaymath}

\subsection{{\color{blue}Minimizando la energ\'ia}}
\label{sec:energia}

Como dijimos anteriormente, nuestro objetivo consiste en buscar m\'inimos
locales \viewref{sec:optimalidad} de la funci\'on de etiquetado; y en el caso
particular de $f$, podemos decir que esta es un m\'inimo local
\cite{Boykov2001} si ocurre

\begin{equation} \label{eq:f_cercana}
E(f) \leq E(f') \textrm{ con $f'$ ``cercana'' a $f$}
\end{equation}

Trabajando con modelos de etiquetados sobre sistemas discretos, los etiquetados
cerca de $f$ son aquellos que se encuentran a un \movement de $f$. Muchas
t\'ecnicas para obtener m\'inimos locales usan lo que \cite{Boykov2001} llama
\standardMovement, que consiste en cambiar la \graphLabel de un solo v\'oxel.
Luego, para \standardMovement \mathref{eq:f_cercana} se lee como: Si $f$ es un
m\'inimo local, con respecto a movimientos standard, entonces no se puede
disminuir la energ\'ia cambiando la etiqueta de un solo v\'oxel.

Dado que los estudios realizados sobre el c\'alculo de energ\'ia utilizando
\standardMovement devuelven soluciones de baja calidad, \cite{Boykov2001} plantea
un modelo utilizando un movimiento que permite que muchos v\'oxeles cambien de
\graphLabel a la vez. Este movimiento se conoce como \alphaExpansion.\\
Para toda funci\'on de etiquetado $f$ existe una relaci\'on uno a uno con una
partici\'on $\P = \{\P_l | l \in \L\}$, siendo $\P_l = \{ p \in \P | f_p = l \}$
el subconjunto de v\'oxeles con \graphLabel $l$. A partir de esta relaci\'on
entre $f$ y $\P$ expresamos \alphaExpansion en t\'erminos de conjuntos de
v\'oxeles. Lo definimos como un \movement de una partici\'on $\P$ a otra
partici\'on $\P'$ si $\P_{\alpha} \subset \P'_{\alpha}$ y para al menos un $l
\neq \alpha$ ocurre que $\P'_l \subset \P_l$.

\subsection{{\color{blue}Obteniendo el \'optimo \alphaExpansion}}
\label{sec:expansion}

Dada una funci\'on de etiquetado $f$ y una \graphLabel $\alpha$, buscamos
encontrar una $f'$ que minimize $E$ con respecto a todo etiquetado posible en un
\movement de $f$ utilizando \alphaExpansion. En esta secci\'on presentamos
una t\'ecnica que resuelve este problema asumiendo que cada funci\'on de
penalizaci\'on V satisface que

\begin{eqnarray} \label{eq:metric}
V(\alpha,\beta) & \Leftrightarrow & \alpha = \beta\\
V(\alpha,\beta) & = & V(\beta,\alpha) \geq 0\\
V(\alpha,\beta) & = & V(\alpha,\gamma) + V(\gamma,\beta) \geq 0
\end{eqnarray}

%Los pasos se encuentran reflejados en el algoritmo

%\begin{framed}
%\begin{verbatim}
%Tomamos una funcion de etiquetado f arbitraria
%Para cada etiqueta a en L
%    Buscamos la f' que minimize E a un movimiento de f
%    usando a-expansion
%    Si E(f') < E(f) entonces f = f'
%Si se logra minimizar E volvemos a 2
%Devolvemos f
%\end{verbatim}

%\end{framed}

Nuestra t\'ecnica se basa en encontrar el corte m\'inimo en un grafo $\G_{\alpha}
= \langle \V_{\alpha}, \E_{\alpha} \rangle$. La estructura de este grafo es
determinada por la partici\'on actual P y por la etiqueta
$\alpha$; de modo que luego de cada iteraci\'on cambia su estructura.\\
Cada nodo de nuestro grafo representa un v\'oxel de la imagen. Luego, a este
conjunto de nodos le agregamos los dos terminales, $\alpha$ y
$\overline{\alpha}$, y los v\'oxeles pertenecientes a $\P$; adicionalmente por
cada par de v\'oxeles $\{p,q\} \in \N$ que se encuentran separados en la
partici\'on actual ($f_p \neq f_q$) crearemos un \textit{nodo auxiliar} $a_{p,q}$
\cite{Boykov2001}. Estos \'ultimos se introducen en los l\'imites entre las
particiones $\P_l$ con $l \in \L$. Siendo el conjunto de v\'ertices

\begin{displaymath}
\V_{\alpha} = \left\{ \alpha, \overline{\alpha}, \P, \bigcup_{\{p,q\} \in \N
\wedge f_p \neq f_q} a_{p,q} \right\}
\end{displaymath}

Cada v\'oxel $p \in \P$ se encuentra conectado a los terminales mediante ejes
$t_{p}^{\alpha}$ y $t_{p}^{\overline{\alpha}}$, llamados $t$-$links$. Cada
$\{p,q\} \in \N$ que no se encuentren separados por la partici\'on $\P$ ($f_p =
f_q$), se conectan mediante un eje $e_{\{p,q\}}$ llamado $n$-$links$; y para cada
par $\{p,q\} \in \N$ tal que $f_p \neq f_q$ creamos un conjunto de tres ejes,
$C_{\{p,q\}} = \left\{ e_{\{p,a\}}, e_{\{a,q\}}, t^{\overline{\alpha}}_{a}
\right\}$ donde $a = a_{\{p,q\}}$ es el correspondiente nodo auxiliar
\figref{fig:expansion} \footnote{\cite{Boykov2001}}.

\begin{displaymath}
E_{\alpha} =\left\{ \bigcup_{p \in
\P}\{t_{p}^{\alpha},t_{p}^{\overline{\alpha}}\}, \bigcup_{\{p,q\} \in \N \wedge f_p \neq f_q} C_{\{p,q\}},
\bigcup_{\{p,q\} \in \N \wedge f_p = f_q} e_{\{p,q\}}
\right\}
\end{displaymath}

Los pesos asignados a los ejes se muestran en la tabla \ref{tbl:pesos}
\footnote{\cite{Boykov2001}}

\begin{table}[htb!!]
\centering
\begin{tabular}{|c|c|c|}\hline
Eje & Peso & para \\
\hline \hline
$t_{p}^{\overline{\alpha}}$ & $\infty$ & $p \in \P_{\alpha}$ \\\hline
$t_{p}^{\overline{\alpha}}$ & $D_p(f_p)$ & $p \notin \P_{\alpha}$ \\\hline
$t_{p}^{\alpha}$ & $D_p(\alpha)$ & $p \in \P_{\alpha}$ \\\hline
$e_{\{p,a\}}$ & $V(f_p,\alpha)$ &  \\\cline{1-1}
$e_{\{a,q\}}$ & $V(\alpha,f_q)$ & $ \{p,q\} \in \N, f_p \neq f_q$ \\\cline{1-1}
$t_{a}^{\overline{\alpha}}$ & $V(f_p,f_q)$ & \\\hline
$e_{\{p,q\}}$ & $V(f_p,\alpha)$ & $ \{p,q\} \in \N, f_p = f_q$ \\\hline
\end{tabular}
\caption{Tabla de Pesos para el grafo basado en \alphaExpansion}
\label{tbl:pesos}
\end{table}

% - fig:expansion
\insertImage{im/expansion}{Ejemplo de grafo
$\G_{\alpha}$ para una im\'agen de 1D. El conjunto de p\'ixeles es
$\P_{\alpha\beta} = \P_{\alpha} \cup  \P_{\beta}$ donde $\P_{\alpha} =
\{p,r,s\}$ y $\P_{\beta} = \{q, \ldots, w\}$ }{fig:expansion}{100mm}

\subsubsection{{\color{blue}Cortes}}

Sea $\G = \langle V, E \rangle$ un grafo con pesos, con dos v\'ertices
distingibles llamados terminales. Definimos un corte $C \subset E$ como un
conjunto de ejes de modo que los terminales est\'en separados en el grafo
inducido $\G(C) = \langle V, E - C \rangle$. Para que ning\'un subconjunto
propio de $C$ separ\'e a los terminales, $C$ debe ser minimal.

Tomando la definici\'on de un corte sobre el grafo, este debe incluir exactamente
un $t$-$link$ por cada pixel $p \in \P$. A partir de esta propiedad definimos
una funci\'on de etiquetado $f^C$ correspondiente al corte $C$ en $\G_{\alpha}$

\begin{displaymath}
f_p^C = \left\{ \begin{array}{llll}
    \alpha & \textrm{si} &  t_p^{\alpha} \in C &\\
    & & & \forall p \in \P \\
    f_p & \textrm{si} &  t_p^{\overline{\alpha}} \in C & \end{array} \right.
\end{displaymath}

En otras palabras, se le asigna una \graphLabel $\alpha$ a un v\'oxel $p$
si el corte $C$ separa a $p$ del terminal $\alpha$, mientras que si $C$ separa a
$p$ de $\overline{\alpha}$ entonces mantiene la etiqueta $f_p$ asignada
anteriormente.

\begin{lemma}
El etiquetado $f^C$ correspondiente al corte $C$ en $\G_{\alpha}$ se encuentra a un
movimiento de distancia del etiquetado inicial $f$ utilizando
\alphaExpansion
\end{lemma}

Es f\'acil ver que el corte $C$ quita un $n$-$link$ $e_{pq}$ entre un par de
v\'oxeles $\{p,q\} \in N$ tal que $f_p = f_q$ si solo si $C$ deja conectados a
$p$ y $q$ con diferentes terminales. Formalmente

\begin{property} \label{eq:cuts}
Para todo corte $C$ y para todo $n$-$link$ $e_{pq}$
\begin{eqnarray} 
\textrm{Si  } t_p^{\alpha}t_q^{\alpha} \in C & \textrm{entonces} & e_{pq} \notin
C \label{eq:cuts:1} \\
\textrm{Si  } t_p^{\overline{\alpha}}t_q^{\overline{\alpha}} \in C &
\textrm{entonces} & e_{pq} \notin C \label{eq:cuts:2} \\
\textrm{Si  } t_p^{\overline{\alpha}}t_q^{\alpha} \in C & \textrm{entonces} &
e_{pq} \in C \label{eq:cuts:3} \\
\textrm{Si  } t_p^{\alpha}t_q^{\overline{\alpha}} \in C & \textrm{entonces} &
e_{pq} \in C \label{eq:cuts:4}
\end{eqnarray}
\end{property}

Las propiedades \mathref{eq:cuts:1} y \mathref{eq:cuts:2} se
desprenden de que el corte $C$ sea minimal. Por su lado,
\mathref{eq:cuts:3} y \mathref{eq:cuts:4} de que $C$ debe
separar a los terminales \figref{fig:cuts} \footnote{\cite{Boykov2001}}.

% - fig:cuts
\insertImage{im/cuts}{Propiedades de un corte $C$ en $\G_{\alpha\beta}$
para dos p\'ixeles $p,q \in \N$ conectados por $n$-link
$e_{p,q}$. Las lineas punteadas muestran los ejes cortados por
$C$ mientras las demas lineas muestran los ejes que permanecen
en el grafo inducido $\G(C) = \langle \V, \E - C \rangle$.}{fig:cuts}{120mm}

A partir de estas propiedaes planteamos el siguiente lema

\begin{lemma}
Para cualquier corte $C$ y para cualquier $n$-$link$ $e_{pq}$
\begin{displaymath}
| C \cap e_{pq} | = V(f_p^C, f_q^C)
\end{displaymath}

\end{lemma}
 
 % ¿ TENGO QUE DEMOSTRAR TODO ESTO ?
 
 Si tomamos el conjunto de ejes $E_{pq}$ correspondientes al par de v\'oxeles
 $\{p,q\} \in \N$ relacionados entre s\'i, tal que $f_p \neq f_q$ y asumiendo
 que $a = a_{p,q}$ es un nodo auxiliar entre el par de nodos correspondientes,
 podemos observar la siguiente propiedad
 
 \begin{property} \label{eq:minCut}
 Si $\{p,q\} \in \N$ y $f_p = f_q$, entonces el corte m\'inimo $C$ en $\G_{\alpha}$
 satisface:
\begin{eqnarray}
\textrm{Si  } t_p^{\alpha}t_q^{\alpha} \in C & \textrm{entonces} & C \cap
E_{pq} = \emptyset \label{eq:minCut:1}\\ 
\textrm{Si  } t_p^{\overline{\alpha}}t_q^{\overline{\alpha}} \in C &
\textrm{entonces} & C \cap E_{pq} = t_a^{\overline{\alpha}}
\label{eq:minCut:2}\\ 
\textrm{Si  } t_p^{\overline{\alpha}}t_q^{\alpha} \in C & \textrm{entonces} &
 C \cap E_{pq} = e_{p,a} \label{eq:minCut:3} \\
\textrm{Si  } t_p^{\alpha}t_q^{\overline{\alpha}} \in C & \textrm{entonces} &
 C \cap E_{pq} = e_{a,q} \label{eq:minCut:4}
\end{eqnarray}
\end{property}

La propiedad \mathref{eq:minCut:1} se deriva del hecho de que ning\'un
subconjunto de $C$ es un corte. \mathref{eq:minCut:2}, \mathref{eq:minCut:3} y
\mathref{eq:minCut:4} se desprenden de el hecho de que $|C|$ es minimal, y de
que $|e_{pa}|$, $|e_{aq}|$ y $|t_a^{\overline{\alpha}}|$ satisfacen la
desigualdad triangular, de modo que cortar cualquiera de los tres ejes es m\'as
economico, en t\'erminos de energ\'ia, que cortar los otros dos.

A partir de la propiedad \mathref{eq:minCut} podemos plantear el
siguiente lema

\begin{lemma}
Si $\{p,q\} \in \N$ y $f_p \neq f_q$, entonces el m\'inimo corte $C$ en
$\G_{\alpha}$ satisface
\begin{eqnarray}
|C \cap E_{p,q}| = V(f_p^C,f_q^C)
\end{eqnarray}
\end{lemma}

La propiedad \mathref{eq:cuts} se satisface para cualquier corte, y la
propiedad \mathref{eq:minCut} solo para los cortes m\'inimos. Igual
as\'i, puede suceder que otros cortes distintos del m\'inimo satisfagan ambas
propiedades. Luego definimos como un corte $elemental$ en $\G_{\alpha}$ aquel que
cumple con ambas propiedades.

\begin{theorem}{\cite{Boykov2001}}
Sea $\G_{\alpha}$ construido a partir de la funci\'on $f$ y de la etiqueta
$\alpha$. Existe luego una correspondencia uno a uno entre los cortes $elementales$ en
$\G$ y el etiquetado obtenido mediante un movimiento de $\alpha$-expansion a
partir de $f$. De este modo para cualquer corte $elemental$ $C$ tenemos que
$|C| = E(f^C)$.
\end{theorem}

De este teorema se desprende el siguiente corolario.

\begin{corollary}
El etiquetado de menor energ\'ia mediante un movimiento de \alphaExpansion a
partir de $f$ es $\hat{f} = f^C$, donde $C$ es el m\'inimo corte en $\G_{\alpha}$.
\end{corollary} 

\section{Propiedad de Optimalidad}

En esta secci\'on probaremos que todo m\'inimo local obtenido mediante
movimientos de \alphaExpansion se encuentra cercano al m\'inimo global, y que
esta distancia, que puede ser tan peque\~na como 2, depende del V que se
utilice. Sea $c$ el radio del mayor valor de V distinto de cero a el m\'inimo
valor de V distinto de cero

\begin{equation}
c = \frac{max_{\alpha \neq \beta \in \L}V(\alpha,\beta)}{min_{\alpha \neq \beta
\in \L}V(\alpha,\beta)}
\end{equation}

Dado que V cumple \ref{eq:metric}, $c$ se encuentra bien definido. Si $V_{p,q}$
tiene valores diferentes para el par de vecinos $p,q$ entonces

\begin{equation}
c = max_{p,q \in \N} \left( \frac{max_{\alpha \neq \beta \in
\L}V(\alpha,\beta)}{min_{\alpha \neq \beta \in \L}V(\alpha,\beta)} \right)
\end{equation}

\begin{theorem}
Sea $\hat{f}$ un m\'inimo local obtenido mediante movimientos de
\alphaExpansion y sea $f^*$ la soluci\'on global \'optima. Entonces $E(\hat{f})
\leq 2cE(f^*)$.
\end{theorem}

\begin{proof}
Dado un $\alpha \in \L$ y sea

\begin{equation} \label{eq:proof_1}
\P_{\alpha} = \left\{ p \in \P | f_p^* = \alpha \right\}
\end{equation} 

Podemos obtener una funci\'on de etiquetado $f^{alpha}$ a un movimiento
de \alphaExpansion de distancia de $\hat{f}$ de la siguiente forma

\begin{equation} \label{eq:proof_2}
f_p^{\alpha} = \left\{
\begin{array}{rl}
  \alpha & \textrm{si } p \in \P_{\alpha} \\
  \hat{f_p} & \textrm{en otro caso }
\end{array} \right.
\end{equation}

Luego dado que $\hat{f}$ es un m\'inimo local, si hacemo un movimiento
de \alphaExpansion 

\begin{equation} \label{eq:proof_3}
E(\hat{f} \leq E(f^{\alpha}))
\end{equation}

Sea $S$ un conjunto de v\'oxeles $\P$ y de pares de v\'oxeles que son vecinos
en $\N$. Luego podemos definir $E(f|S)$ como la restricci\'on de la energ\'ia
de la funci\'on de etiquetado $f$ al conjunto $S$

\begin{equation}
E(f|S) = \sum_{p \in S} D_p(f_p) + \sum_{\{p,q\} \in S} V(f_p,f_q)
\end{equation}

Sea $I^{\alpha}$ el conjunto de v\'oxeles y pares de v\'oxeles vecinos
contenidos en $\P_{\alpha}$, $B^{\alpha}$ el conjunto de pares de
v\'oxeles vecinos en el borde de $\P_{\alpha}$ y $O^{\alpha}$ el conjunto de
v\'oxeles y pares de v\'oxeles vecinos fuera de $\P_{\alpha}$.

\begin{displaymath}
\begin{array}{ccccc}
I^{\alpha} & = & \P_{\alpha} & \cup & \{\{p,q\} \in \N : p \in \P_{\alpha}, q
\in P_{\alpha}\} \nonumber \\
B^{\alpha} & = & & & \{\{p,q\} \in \N : p \in \P_{\alpha}, q
\notin P_{\alpha}\} \nonumber \\
O^{\alpha} & = & (\P - \P_{\alpha}) & \cup & \{\{p,q\} \in \N : p \notin
\P_{\alpha}, q \notin P_{\alpha}\} \nonumber
\end{array}
\end{displaymath}

A partir de estos conjuntos se observa

\begin{eqnarray}
E(f^{\alpha}|O^{\alpha}) & = & E(\hat{f}|O^{\alpha}) \label{eq:prop_1} \\
E(f^{\alpha}|I^{\alpha}) & = & E(f^*|I^{\alpha}) \label{eq:prop_2}\\
E(f^{\alpha}|B^{\alpha}) & = & E(f^*|B^{\alpha}) \label{eq:prop_3}
\end{eqnarray}

Las ecuaciones \ref{eq:prop_1} y \ref{eq:prop_2} se deducen de \ref{eq:proof_2}
y \ref{eq:proof_1}, mientras que \ref{eq:prop_3} se obtiene de que para cualquier
$\{p,q\} \in B^{\alpha}$, tenemos que $V(f^{\alpha}_p, f^{\alpha}_q) \leq
cV(f^*_p, f^*_q) \neq 0$.\\
Dado que $I^{\alpha} \cup B^{\alpha} \cup O^{\alpha}$ contiene todos los
v\'oxeles de $\P$ y todos los pares de vecinos en $\N$, podemos expandir
\ref{eq:prop_3}

\begin{equation}
E(\hat{f}|I^{\alpha}) + E(\hat{f}|B^{\alpha}) + E(\hat{f}|O^{\alpha}) \leq
E(f^{\alpha}|I^{\alpha}) + E(f^{\alpha}|B^{\alpha}) + E(f^{\alpha}|O^{\alpha})
\nonumber
\end{equation}

Usando \ref{eq:prop_1}, \ref{eq:prop_2} y \ref{eq:prop_3} a partir de la
ecuaci\'on anterior obtenemos:

\begin{equation} \label{eq:prop_4}
E(\hat{f}|I^{\alpha}) + E(\hat{f}|B^{\alpha}) \leq
E(f^*|I^{\alpha}) + cE(f^*|B^{\alpha})
\end{equation}

Para obtener un l\'imite de la energ\'ia total necesitamos la suma de
\ref{eq:prop_4} para todas las etiquetas $\alpha \in \L$:

\begin{equation} \label{eq:prop_5}
\sum_{\alpha \in \L}(E(\hat{f}|I^{\alpha}) + E(\hat{f}|B^{\alpha})) \leq
\sum_{\alpha \in \L}(E(f^*|I^{\alpha}) + cE(f^*|B^{\alpha}))
\end{equation}

Sea $B = \bigcup_{\alpha \in \L} B^{\alpha}$, se puede observar que para cada
par $\{p,q\} \in B$, el termino $V(\hat{f}_p,\hat{f}_q) = E(\hat{f}|\{p,q\})$
aparece dos veces en el lado izquierdo de \ref{eq:prop_5}, una vez en
$E(\hat{f}|B^{\alpha})$ para $\alpha = f^*_p$, y una vez en
$E(\hat{f}|B^{\alpha})$ para $\alpha = f^*_q$. Del mismo modo, cada
$V(f^*_p,f^*_q) = E(f^*|\{p,q\})$ aparece dos veces en el lado derecho de
\ref{eq:prop_5}. Luego, \ref{eq:prop_5} se puede reescribir

\begin{displaymath}
E(\hat{f}) + E(\hat{f}|B) \leq E(f^*) + (2c - 1)E_B(f^*) \leq 2cE(f^*)
\end{displaymath}
\end{proof}


